Skip to main content

배열 vs 연결리스트

배열​

  • 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
  • 메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에, index를 통한 접근이 용이하다.
  • 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.
  • 시간복잡도
    • 탐색: O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n)
    • 삽입 및 삭제:
      • 배열의 처음 또는 중간에 삽입 및 삭제: O(n) 삽입 지점 이후의 데이터를 옮겨야 하기 때문이다.
      • 배열의 끝에 삽입 및 삭제: O(1)

array

연결리스트​

  • 연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다.
  • 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다.
  • 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
  • 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
  • 시간복잡도
    • 탐색: O(n)
    • 삽입 및 삭제: 삽입과 삭제 자체는 O(1) 이다.
      • 연결리스트의 처음에 삽입 및 삭제: O(1)
      • 연결리스트의 중간에 삽입 및 삭제: O(n) 탐색시간 소요
      • 연결리스트의 끝에 삽입 및 삭제:
        • 끝을 가리키는 별도의 포인터를 갖는 경우: O(1)
        • 끝을 가리키는 별도의 포인터를 갖지 않는 경우: O(n) 탐색시간 소요

linked_list

연결리스트 연산​

삽입​

  1. 노드를 생성하고, 삽입하려는 위치를 찾는다. linked_list_insertion_0
  2. 삽입할 노드를 NewNode라고 하면, NewNode가 그 다음 노드를 가리키게 한다. NewNode.next -> RightNodelinked_list_insertion_1
  3. 새로 삽입한 노드의 이전 노드가 새로운 노드를 가리키게 한다. LeftNode.next -> NewNodelinked_list_insertion_2

삭제​

  1. 탐색을 통해 삭제하고자 하는 노드 (TargetNode)를 찾는다. linked_list_deletion_0
  2. TargetNode의 왼쪽 노드가 TargetNode의 오른쪽 노드를 가리키게 한다. LeftNode.next -> TargetNode.nextlinked_list_deletion_1
  3. TargetNode가 RightNode를 가리키지 않게 한다. TargetNode.next -> NULLlinked_list_deletion_2

배열과 연결리스트 비교​

배열연결리스트
장점인덱스를 통한 빠른 접근이 가능하다.삽입과 삭제가 용이하다.
단점삽입과 삭제가 오래 걸린다.
배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.		임의 접근이 불가능하여, 처음부터 탐색을 진행해야 한다.
용도빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

이중 연결리스트와 원형 연결리스트​

이중 연결리스트​

  • 이중 연결리스트는 위에서 언급한 연결리스트(단순 연결리스트)와 다르게 전, 후로 탐색이 가능한 구조이다.

  • 즉, 단순 연결리스트의 노드는 데이터와 다음 노드의 주소를 저장한다면, 이중 연결리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장하게 된다.

  • 장점

    • 단순 연결리스트에서는 최악의 경우 n번의 탐색을 해야하지만, 이중 연결리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝다면 tail에서 부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.

원형 연결리스트​

  • 원형 연결리스트는 단순 연결리스트의 마지막 노드가 null을 가리키는게 아닌, 처음 노드를 가리키는 구조이다.
  • 즉, head에서부터 순회를 반복적으로 진행하다보면 다시 처음으로 돌아오는 구조이다.
  • 이중 연결리스트도 마지막 노드가 처음 노드를 가리키는 구조가 되면, 이를 이중 원형 연결리스트라고 한다.

예상 면접 질문​

  • 배열 또는 연결리스트의 특징과 그로 인해 갖는 장단점은 ?
  • 배열 또는 연결리스트를 사용하면 좋을 데이터의 예시와 이유

참고​

기여자​


Junho Moon
📦